В теории алгебраических байесовских сетей стоит задача построения вторичной структуры сети по известной первичной структуре. Для осуществления логико-вероятностного вывода в качестве вторичной структуры может выступать только минимальный граф смежности. В статье сформирован алгоритм рандомизированного синтеза минимального графа смежности. Доказана теорема о том, что выбор любого возможного для заданной первичной структуры алгебраической байесовской сети минимального графа смежности алгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиалгебраические байесовские сетиимеет положительную вероятность.
Условием работы алгоритмов глобального логико-вероятностного вывода в алгебраической байесовской сети (АБС) является отсутствие циклов в ее вторичной структуре. Первичная структура, над которой можно построить ациклическую вторичную, называется ациклической. Цель работы — предложить алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в ее вторичной структуре без непосредственного построения вторичной структуры, а также оценка сложности этого алгоритма. В работе сформулирован алгоритм выявления ацикличности первичной структуры на основе оценки числа ребер в минимальном графе смежности полным перебором, доказана его корректность, оценена его сложность, предложено улучшение скорости работы этого алгоритма, доказана корректность и оценено время работы улучшенного алгоритма. Также рассмотрены возможности улучшения скорости работы этого алгоритма за счет использования алгоритмов построения элементов третичной полиструктуры АБС.
Цель данной работы — обобщение результатов структурного анализа минимальных графов смежности, представляющих вторичную структуру алгебраической байесовской алгебраической сети, на графы смежности общего вида, представляющие эту же структуру. Сформулирована система терминов, расширяющая существующую систему для МГС на графы смежности в целом. Исследованы новые свойства графов смежности. Сформулированы и доказаны две леммы, характеризующие оммаж (результат сжатия минимального графа смежности) как минимальную курию (результат сжатия графа смежности). Упрощено доказательство теоремы о множестве минимальных графов смежности.
1 - 3 из 3 результатов